3. 无人机巡检航线规划[200分]

题目内容

某电力公司使用无人机对 n 个电力塔进行巡检。每个电力塔 i 位于坐标 (x_i, y_i)，无人机从基地（坐标 (0,0)）出发，需要依次飞达每个电力塔完成巡检后结束任务，无需返回基地。

无人机同一时刻只能飞向一个电力塔，请规划巡检顺序，使无人机飞行的总距离最短（两个坐标点间按曼哈顿距离计算，即 |x_1-x_2| + |y_1-y_2|），输出最短总距离。

输入描述

• n：电力塔数量，1 ≤ n ≤ 15
• x_i, y_i：第 i 个电力塔的坐标，0 ≤ x_i, y_i ≤ 200

输出描述

输出最短总距离（整数）。

样例

样例 1

输入

3
1 2
3 1
2 3

输出

8

说明： 3 个电力塔：A(1,2)、B(3,1)、C(2,3)。基地为 O(0,0)。

• 巡检顺序 A → C → B：O → A 距离 |1-0|+|2-0|=3，A → C 距离 |1-2|+|2-3|=2，C → B 距离 |2-3|+|3-1|=3。总距离 3+2+3=8
• 巡检顺序 A → B → C：O → A 距离 3，A → B 距离 |1-3|+|2-1|=3，B → C 距离 |3-2|+|1-3|=3。总距离 9
• 巡检顺序 B → A → C：O → B 距离 4，B → A 距离 3，A → C 距离 2。总距离 9

其余顺序总距离均不小于 8，最短总距离为 8。

样例 2

输入

2
1 1
2 2

输出

4

说明： 2 个电力塔：A(1,1)、B(2,2)。基地为 O(0,0)。

• 巡检顺序 A → B：O → A 距离 |0-1|+|0-1|=2，A → B 距离 |1-2|+|1-2|=2。总距离 2+2=4
• 巡检顺序 B → A：O → B 距离 |0-2|+|0-2|=4，B → A 距离 |2-1|+|2-1|=2。总距离 4+2=6

最短总距离为 4。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let inputs = [];
rl.on('line', (input) => {
    inputs.push(input.split(' ').map(Number));
})
rl.on('close', () => {
    const n = inputs.shift()[0];
    const arr = inputs;
    
    // ========== 优化1：预计算距离矩阵 ==========
    // d[i][j] 表示塔 i 到塔 j 的曼哈顿距离
    const d = Array.from({length: n}, () => Array(n).fill(0));
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            d[i][j] = Math.abs(arr[i][0] - arr[j][0]) + Math.abs(arr[i][1] - arr[j][1]);
        }
    }
    
    const used = new Array(n).fill(false);  // 标记哪些塔已访问
    let count = 0;                          // 已访问数量，替代 filter
    const memo = new Map();                 // 记忆化缓存
    
    // ========== 优化2：dfs 返回"剩余距离" ==========
    // dfs(c) 表示：当前站在塔 c，飞完所有还没访问的塔，最少还要飞多远
    const dfs = (c) => {
        // 全部飞完了，剩余距离为 0
        if(count === n) return 0;
        
        // 用"当前位置 + 当前访问状态"作为缓存 key
        // 例如："2,true,false,true" 表示在2号塔，0号和2号已访问
        const key = c + ',' + used.join(',');
        if(memo.has(key)) return memo.get(key);
        
        let minExtra = Infinity;
        
        for(let i = 0; i < n; i++) {
            if(!used[i]) {
                used[i] = true;   // 去 i 号塔
                count++;          // 访问数 +1
                
                // 从 c 飞到 i 的距离 + 从 i 继续飞完剩下的距离
                const dist = d[c][i] + dfs(i);
                if(dist < minExtra) minExtra = dist;
                
                count--;          // 回溯：恢复访问数
                used[i] = false;  // 回溯：恢复状态
            }
        }
        
        memo.set(key, minExtra);
        return minExtra;
    }
    
    let ans = Infinity;
    for(let i = 0; i < n; i++) {
        used[i] = true;
        count = 1;
        
        // 总距离 = 基地(0,0)到 i 的距离 + 从 i 飞完剩余的距离
        const total = (arr[i][0] + arr[i][1]) + dfs(i);
        if(total < ans) ans = total;
        
        used[i] = false;
        count = 0;
    }
    
    console.log(ans);
})